The present invention relates to a method of configuring a routing table (route search table) used in a packet transfer apparatus arranged at a network relay point.
Due to rapid increase in recent Internet traffic, higher-speed packet transfer techniques are required for a packet transfer apparatus arranged at network relay points. When a packet is received, the packet transfer apparatus determines, according to a destination address included in the packet, one of the networks connected to the packet transfer apparatus and then transfers the packet to the network. To determine the packet transfer destination according to the destination address included in the packet, the packet transfer apparatus uses a routing table (route search table).
The routing table includes a plurality of route entries. Each route entry includes a prefix, i.e., the upper bits of an Internet Protocol (IP) address which indicate a network and a next hop IP address and an output port number which correspond to the prefix. When a packet is received as an input, the packet transfer apparatus searches the routing table for a route entry of which the prefix matches the upper bits of the destination IP address of the packet to recognize the contents of the route entry as the next hop IP address and the output port number for the input packet.
The destination search operation is a process which is possibly a bottleneck in the packet transfer process. The higher the communication speed of the network is, the more serious the problem of the bottleneck is. Additionally, due to increase in the recent Internet traffic, the number of registration entries required for the routing table becomes greater. This also is a problem of the packet transfer apparatus. To cope with the problems, as described in RFC1519, Classless Inter-Domain Routine (CIDR) in which an IP address is divided into a network address and a host address according to an arbitrary prefix position was introduced for an efficient use of an IP address space about the middle of 1990. CIDR slightly lowered the growth rate of the number of required entries in the routing table. However, according to Internet Protocol version 4 (IPv4) Border Gateway Protocol (BGP) Report, the number of routing table entries required for a packet transfer apparatus in the network core reached about a little more than 180 thousand at the end of 2004.
CIDR brings about an advantage of reduction in the number of entries required to be stored in the routing table. However, CIDR requires “longest prefix match” in the search and hence causes at the same time a disadvantage that the routing table search process becomes complicated. That is, there exists possibility that a plurality of entries of the routing table match the search condition as a result of the search. Therefore, it is required to select, from the entries as the search result, one entry including the largest number of bits matching the search condition (longest prefix match).
The routing table search will be concretely described by use of a routing table shown in FIG. 2. The routing table 1000 of FIG. 2 includes six entries 1000-1 to 1000-6 in which the IP address is expressed by eight bits. Each entry (1000-1 to 1000-6) includes an IP address condition which is information equivalent to a prefix and a next hop IP address and an output port number which correspond to the IP address condition. The IP address condition is information including a prefix expressed by the upper bits and a mask (*) expressed by the remaining bits of the IP address. For example, “01111***” of the entry 1000-2 indicates that the upper five bits are “01111” and the lower three bits may be either one of “000”, “001”, “010”, “011”, “100”, “101”, “110”, and “111”. Additionally, “01111***”, “0110****”, “1010****”, “101*****”, and “01******” respectively of the entries 1000-2 to 1000-6 may also be expressed as “01111/5”, “0110/4”, “1010/4”, “101/3”, and “01/2”, respectively. The numeral after the slash is called “prefix length” and indicates the length of the portion of the prefix excepting the mask.
Assume that a packet with, for example, a destination address “01111010” in binary notation is inputted to the packet transfer apparatus. In this case, although the IP address conditions respectively of two entries 1000-2 and 1000-6 match the destination IP address of the input packet, the entry 1000-2 has the longer prefix length and hence the next hop IP address B and the output port number 3 of the entry 1000-2 are determined as the match result.
To increase the operation speed of the routing table search, a recent high-end packet transfer apparatus employs a memory device called “Ternary Contents Addressable Memory (TCAM)” in many cases. For example, “Next Generation Routers” invited paper, IEEE Proceeding, vol. 90, no. 9, pp. 1518-1558, September 2002 and IDT White Paper “Optimum Search Methods for Switch/Router Databases in Access and Metro Edge Networks” describe a method in which the routing table search and the flow discrimination process are implemented at a high speed using the TCAM.
In the TCAM, for each bit of the matching condition, it is possible to designate three kinds of values, namely, “0”, “1”, and “* (Don't Care Mark)”. The TCAM includes a plurality of entries each of which stores a matching condition including a plurality of bits. When a search key is inputted thereto, the TCAM compares the search key with the matching condition of each entry simultaneously for all entries. The TCAM selects, from the addresses of entries matching the search condition, an address value with a highest priority level (e.g., the smallest address value) to output the address value therefrom. By beforehand storing an IP address condition having the longest prefix in an entry of a higher priority level, the TCAM can achieve the longest prefix match.
The TCAM is a memory device suitable for the high-speed routing table search. However, when compared with a Dynamic Random Access Memory (DRAM) and a Static Random Access Memory (SRAM), the TCAM has a problem. That is, power consumption of the TCAM is greater than that of the DRAM and the SRAM by about two orders of magnitude, the integration degree thereof is lower than that of the DRAM and the SRAM, and the TCAM is most expensive.
In a packet transfer apparatus of today, a control card 300 includes the routing table 301 and each line card 100-i (i=1 to N) includes a perfect routing table 210 as shown in FIG. 3. The perfect routing table 210 is disposed to search routing table information at a high speed in an independent way and includes a copy of the contents of the routing table 301, the contents being configured in a format suitable for the hardware to conduct the search. In high-end packet transfer apparatuses in recent years, the TCAM is employed for the routing table of each line card depending on cases.
JP-A-2004-221807 describes a method in which the routing table and the search engine thereof are improved in a network transfer apparatus. To enlarge the capacity, to reduce delay in operation (to increase the operation speed), and to lower the cost of the network transfer apparatus, routing table information of the control card is divided into subset information groups to be allocated as distributed routing tables in the respective line cards. Additionally, each distributed routing table includes a routing table cache to store therein a copy of a part of the information contained in the routing table. If a search does not hit any information item in a routing table cache, a search is made for a destination through the routing table corresponding to the routing table cache.